package com.demo.structure.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 环形队列
 * 队满条件：(tail + 1) % capacity = head 即队尾 + 1 % 容量 = 队首
 * 队空条件：head = tail (队首 = 队尾）
 * 有效数据个数：(tail - head + capacity) % capacity 即 （队尾 - 队首 + 容量） % 容量
 *
 * @author: 蔡奇峰
 * @date: 2020/7/3 22:01
 **/
public class RingQueue {
    /**
     * 容量（实际会小1）
     */
    private int capacity;
    /**
     * 队首（指向真实的队首）
     */
    private int head;
    /**
     * 队尾（指向真实的队尾）
     */
    private int tail;
    /**
     * 环形队列
     */
    private int[] queue;

    /**
     * 初始化
     *
     * @param capacity
     */
    public RingQueue(int capacity){
        this.capacity = capacity;
        this.queue = new int[this.capacity];
    }

    /**
     * 队列是否为空
     *
     * @return
     */
    public boolean isEmpty(){
        return this.head == this.tail;
    }

    /**
     * 是否队满
     *
     * @return
     */
    public boolean isFull(){
        return (this.tail + 1) % this.capacity == this.head;
    }

    /**
     * 入队
     *
     * @param node
     * @return
     */
    public int add(int node) {
        if (isFull()) {
            throw new RuntimeException("入队失败！队满了！");
        }
        this.queue[this.tail] = node;

        this.tail = (this.tail + 1) % this.capacity;
        return node;
    }

    /**
     * 出队
     *
     * @return
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空！出队失败！");
        } else {
            int value = this.queue[this.head];
            this.head = (head + 1) % capacity;
            return value;
        }
    }


    /**
     * 显示队列（只显示有效数据）
     */
    public void displayQueue() {
        int[] queue = this.queue;
        for (int i = 0; i < getSize(); i ++) {
            System.out.printf("%d\t", queue[i]);
        }
        System.out.println();
    }


    /**
     * 显示头部（不是出队）
     */
    public void getHead() {
        System.out.printf("头部数据：%d\t", this.queue[head]);
    }

    /**
     * 获取有效数据的个数
     *
     * @return
     */
    public int getSize(){

        return (tail + capacity - head) % capacity;
    }
}

class RingDemo{

    public static void main(String[] args) {
        // 创建队列 实际上只能装3个
        RingQueue queue = new RingQueue(4);
        System.out.println("队列是否为空：" + queue.isEmpty());
//        System.out.println("出队：" + queue.pop());
        System.out.println("队列是否队满：" + queue.isFull());
        System.out.println("入队：" + queue.add(6));
        System.out.println("显示队列：");
        queue.displayQueue();

        // 入队
        queue.add(8);
        queue.add(14);
        System.out.println("队列是否队满：" + queue.isFull());
//        System.out.println("入队：" + queue.add(88));
        System.out.println("显示队列：");
        queue.displayQueue();

        // 出队
        System.out.println("出队：" + queue.pop());
        // 显示头部
        queue.getHead();
    }

}